﻿using System.Collections;
using System.Collections.Generic;

namespace Hsenl {
    /*
     * 针对通用树结构的子级枚举器, 比如像entity和node这种.
     *
     * 以 Node 为例, 给 Node 继承 IGeneralTree<Node> 接口, 然后在 Node 里写一个方法
     * public IGeneralTree<Node>.GeneralTreeEnumerable ForeachChildren() {
     *      return new IGeneralTree<Node>.GeneralTreeEnumerable(this);
     * }
     *
     * 然后就可以在外部调用
     * foreach (var child in node.ForeachChildren()) {
     *     log(child.xxxx);
     * }
     * 就可以遍历node下所有的子级.
     * 优点: 无GC、性能优异、不暴漏内部的 children 指针、书写便捷
     * 缺点: 内部使用了池、对接口的返回值要求比较苛刻
     */
    public interface IGeneralTree<T> where T : IGeneralTree<T> {
        protected IList<T> Children { get; }

        public readonly struct GeneralTreeEnumerable : IEnumerable {
            private readonly T root;

            public GeneralTreeEnumerable(T root) {
                this.root = root;
            }

            public GeneralTreeEnumerator GetEnumerator() => new GeneralTreeEnumerator(this.root);
            IEnumerator IEnumerable.GetEnumerator() => new GeneralTreeEnumerator(this.root);
        }

        public struct GeneralTreeEnumerator : IEnumerator<T> {
            private Queue<T> _queue;

            public T Current { get; private set; }

            object IEnumerator.Current => this.Current;

            public GeneralTreeEnumerator(T root) {
                this._queue = QueuePool<T>.Rent();
                this.Current = root;

                var children = root.Children;
                if (children != null) {
                    for (int i = 0, len = children.Count; i < len; i++) {
                        var child = children[i];
                        this._queue.Enqueue(child);
                    }
                }
            }

            public bool MoveNext() {
                while (this._queue.Count > 0) {
                    var node = this._queue.Dequeue();
                    this.Current = node;
                    var children = node.Children;
                    if (children != null) {
                        for (int i = 0, len = children.Count; i < len; i++) {
                            var child = children[i];
                            this._queue.Enqueue(child);
                        }
                    }

                    return true;
                }

                return false;
            }

            public void Reset() { }

            public void Dispose() {
                QueuePool<T>.Return(this._queue);
                this._queue = null!;
            }
        }

        public static class QueuePool<TType> {
            private static readonly Stack<Queue<TType>> _pool = new();

            public static Queue<TType> Rent() {
                lock (_pool) {
                    return _pool.Count > 0 ? _pool.Pop() : new Queue<TType>();
                }
            }

            public static void Return(Queue<TType> queue) {
                queue.Clear();
                lock (_pool) {
                    if (_pool.Count > 10) // 因为只在嵌套使用的时候, 才会拓展池子, 所以没必要设置这么大
                        return;
                    _pool.Push(queue);
                }
            }
        }
    }
}